package skiplist;

import jdk.nashorn.internal.ir.ReturnNode;

import java.util.Comparator;

/**
 * @Author: LDeng
 * @Date: 2021-05-05 14:33
 */
public class SkipList<K, V> {
    //节点的next最高层数
    private static final int MAX_LEVEL = 32;

    private static final double P = 0.25;

    public int size;
    //比较器
    private Comparator<K> comparator;
    //首节点，不存放任何K-V
    private Node<K, V> first;
    //有效层数
    private int level = 4;

    public SkipList() {
        this(null);
    }

    public SkipList(Comparator<K> comparator) {
        this.comparator = comparator;
        first = new Node<>(null, null, MAX_LEVEL);//带32个空next的节点
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public V put(K key, V value) {
        keyCheck(key);
        Node<K, V> node = first;
        Node<K, V>[] prevs = new Node[level];//存放往下走的节点
        for (int i = level - 1; i >= 0; i--) {
            int cmp = -1;
            while ((node.nexts[i] != null) && (cmp = compar(key, node.nexts[i].key))>0) {
                //传进来的key比node上的key要大
                //并且不是最后的空节点
                node = node.nexts[i]; //拿当前节点的下一个节点赋值给当前节点 然后下一轮比较
            }
            if (cmp == 0) {//节点存在=>覆盖value, 注意此时节点node是 前一个节点， 覆盖的时候nexts[i]的值
                V oldValue = node.nexts[i].value;
                node.nexts[i].value = value;
                return oldValue;
            }
            prevs[i] = node;
        }
        //能来到这里表示此时的node就是前驱节点
        //添加新节点 层数随机
        int newLevel = randomLevel();
        Node<K, V> newNode = new Node<>(key, value, newLevel);
        //维护指针
        for (int i = 0; i < newLevel; i++) {
            //维护前驱和后继
            if (i >= level) {//新节点level 大于之前的level,跟新首节点的当前层级的next指向新节点
                first.nexts[i] = newNode;
            } else {//更新新节点点的next 和原节点的next
                newNode.nexts[i] = prevs[i].nexts[i];
                prevs[i].nexts[i] = newNode;
            }
        }
        size++;
        //更新层数
        level = Math.max(level, newLevel);
        return null;
    }

    public V get(K key) {
        keyCheck(key);
        //顶层
        Node<K, V> node = first;
        for (int i = level - 1; i >= 0; i--) {
            int cmp = -1;
            while ((node.nexts[i] != null) && (cmp = compar(key, node.nexts[i].key))>0) {
                //传进来的key比node上的key要大
                //并且不是最后的空节点
                node = node.nexts[i]; //拿当前节点的下一个节点赋值给当前节点 然后下一轮比较
            }
            //传进来的key比node上的key要相等或小
            if (cmp == 0) return node.nexts[i].value;
        }
        return null;
    }

    public V remove(K key) {
        keyCheck(key);
        Node<K, V> node = first;
        Node<K, V>[] prevs = new Node[level];//存放往下走的节点
        boolean exist = false;
        for (int i = level - 1; i >= 0; i--) {
            int cmp = -1;
            while ((node.nexts[i] != null) && (cmp = compar(key, node.nexts[i].key))>0) {
                node = node.nexts[i]; //此时node是要查找节点第0层的前驱节点
            }
            prevs[i] = node;
            if (cmp == 0) exist = true;
        }
        if (!exist) return null;//不存在
        size--;

        //需要被删除的节点
        Node<K, V> removedNode = node.nexts[0];
        //更新前驱节点的指针
        for (int i = 0; i < removedNode.nexts.length; i++) {
            prevs[i].nexts[i] = removedNode.nexts[i];
        }
        //更新level
        int newLevel = level;
        while (--newLevel >= 0 && first.nexts[newLevel] == null) {
            level = newLevel;
        }
        return removedNode.value;
    }

    private int randomLevel() {
        //模仿Redis
        int level = 1;
        while (Math.random() < P && level < MAX_LEVEL) {
            level++;
        }
        return level;
    }


    private void keyCheck(K key) {
        if (key == null) {
            throw new IllegalArgumentException("KEY不能为空");
        }
    }

    private int compar(K k1, K k2) {
        return comparator != null ? comparator.compare(k1, k2) :
                ((Comparable<K>) k1).compareTo(k2);
    }

    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V>[] nexts;//数组的层数，一般为32层

        public Node(K key, V value, int level) {
            this.key = key;
            this.value = value;
            nexts = new Node[level];
        }
        @Override
        public String toString() {
            return key + ":" + value + "_" + nexts.length;
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("一共" + level + "层").append("\n");
        for (int i = level - 1; i >= 0; i--) {
            Node<K, V> node = first;
            while (node.nexts[i] != null) {
                sb.append(node.nexts[i]);
                sb.append(" ");
                node = node.nexts[i];
            }
            sb.append("\n");
        }
        return sb.toString();
    }


}
